package chapter02;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GetPermutation60 {
    /**
     * 数学规律
     * 1...n n个数的排列 找第k个
     * 规律：将1~n 从小到大存放在数组nums中
     *       假设第一个位置为1 还有n-1个数 共(n-1)!种排列
     *       那么我们可以确定第一个数在nums中下标  index=(k-1)/(n-1)!
     *       也可以计算出当前位置数字确定之前共index*(n-1)!中排列
     *       求出当前位置数字后 将nums[index]数字删除
     *       下一个位置求出第k'小   k'=k-index*(n-1)
     *       循环求出其他位置数字
     */
    public String getPermutation(int n, int k){
        int[] fn=new int[n];
        List<Integer> numList=new ArrayList<>();
        numList.add(1);
        fn[0]=1;
        for(int i=1;i<n;i++){
            fn[i]=fn[i-1]*i;
            numList.add(i+1);
        }
        StringBuffer str=new StringBuffer();
        while (n>0){
            int index=(k-1)/fn[n-1];
            k=k-index*fn[--n];
            str.append(numList.get(index));
            numList.remove(index);
        }
        return str.toString();
    }

    //下一个排列 参考NextPermutation
    public String getPermutation1(int n, int k) {
        char[] s=new char[n];
        for(int i=1;i<=n;i++){
            s[i-1]=(char)(i+'0');
        }
        int i,j,count=1;
        int flag;
        while (k!=count){
            flag=0;
            for(i=s.length-2;i>=0&&count!=k;i--){
                for(j=s.length-1;j>i&&count!=k;j--){
                    if(s[i]<s[j]){
                        swap(s,i,j);
                        count++;
                        Arrays.sort(s,i+1,s.length);
                        flag=1;
                        break;
                    }
                }
                if(flag==1){
                    break;
                }
            }
        }
        return String.valueOf(s);
    }

    public void swap(char[] s,int i,int j){
        char c=s[i];
        s[i]=s[j];
        s[j]=c;
    }

}
